Interleaving is a method of sequentially separating a data block into units, such as bytes, and then transmitting the units out of sequence in a deterministic manner. A receiver uses an inverse of the interleaving method to reorder the received bytes and reproduce the data block. Digital communication systems that communicate over channels subject to bursty noise can employ interleaving in combination with error correction to reduce data error rates through the channel. Communicating the units out of sequence reduces the probability that a noise burst will corrupt sequential data units in the data block. Interleaving thereby increases the probability that the error correcting code will be able to recover data that was corrupted in the channel.
Referring now to FIG. 1, a block diagram is shown of an interleaving communication system 10 according to the prior art. An encoder 12 receives the data block 14 and encodes it with the error correcting code. An interleaver 16 receives the encoded data block and performs the interleaving operation to reorder bytes of the data block in a deterministic manner. Interleaver 16 then communicates the interleaved bytes to a transmitter 18 for transmission through channel 20.
Bursty noise may exist on channel 20 that corrupts some of the interleaved bytes as they propagate to a receiver 22. A deinterleaver 24 receives the corrupted and interleaved bytes from receiver 22 and deinterleaver them according to an inverse of the interleaving method employed by interleaver 16. A decoder 26 receives the deinterleaved bytes and performs an error correction operation to recover data from the corrupted bytes and reproduce the data block at output 28. Whether decoder 26 succeeds in recovering the data is based on the type of error correcting code being used, the duration and frequency of the bursty noise in channel 20, and the interleaving depth, which is described below.
There are many types of interleaving schemes that have been proposed and implemented in modern digital communication systems. One popular scheme is block interleaving (BI) and is used in systems such as wireless LAN (WLAN). Referring now to FIG. 2A, operation of interleaver 16 and deinterleaver 24 will be described as they implement the BI scheme. Bytes b0 . . . b11 of an example encoded data block 30 are shown. Interleaver 16 and deinterleaver 24 include respective ping-pong memories that are conceptually partitioned into N rows and D columns, where D and N can be any positive integers. D represents the interleaving depth and N represents an interleaving block.
The memory space of interleaver 16 is shown as matrices 32-1 and 32-2 having D=2 columns and N=3 rows. Interleaver 16 writes bytes (b0 . . . b5) from data block 30 to matrix 32-1 in column-by-column fashion until matrix 32-1 is full. After matrix 32-1 is full, interleaver 16 writes bytes (b6 . . . b11) from data block 30 to matrix 32-2 in column-by-column fashion. While interleaver 16 is writing bytes (b6 . . . b11) into matrix 32-2, interleaver 16 also reads bytes (b0 . . . b5) out from matrix 32-1 in row-by-row fashion to be transmitted in the order shown at 34. After data bytes (b6 . . . b11) have been written into matrix 32-2 and data bytes (b0 . . . b5) have been read from matrix 32-1, interleaver starts writing data into matrix 32-1 column-by-column and reading data out from 32-2 row-by-row. Interleaver 16 repeats the writing and reading processes via respective ones of the matrices 32 until the entire data block 30 has been interleaved. These processes are repeated every N*D period.
The deinterleaver memory is shown as matrices 36-1 and 36-2 that have the same dimension as matrices 32. Deinterleaver 24 writes received bytes 34 into matrix 36-1 row-by-row (e.g., (b0,b3), (b1,b4), (b2,b5)) until matrix 36-1 is full. After matrix 36-1 is full, deinterleaver 24 writes bytes (b6 . . . b11) into matrix 36-2 row-by-row and reads data (b0 . . . b5) out from matrix 36-1 column-by-column. Deinterleaver 24 repeats the writing and reading processes via respective ones of the ping-pong RAMs until all of the bytes at 34 have been processed. These processes are repeated every (N*D) period. The bytes read from deinterleaver 24 form a reconstructed data block 38 that has the same byte order as data block 30.
BI is straightforward to implement, however the ping-pong memory size is 2*N*D bytes in interleaver 16 and in deinterleaver 24. This requirement causes the ping-pong memories to become undesirably large and expensive as the interleaving depth D increases.
The International Telecommunication Union (ITU) has published specifications 992.1, 992.3, and 993.1, which are hereby incorporated by reference in their entirety, that outline a new interleaving scheme named general convolutional interleaving (GCI). GCI is being used for interleaving over asynchronous digital subscriber line (ADSL) and very high bit-rate digital subscriber line (VDSL1) telephone networks. GCI can also be used for interleaving over wireless communication channels.
Referring now to FIG. 2B, operation of interleaver 16 and deinterleaver 24 will be described as they implement the GCI scheme. GCI delays every byte of the N repetitive data blocks by a fixed pattern. It delays the first byte of every N-byte sequence by 0 bytes, the 2nd byte of every N-byte sequence by (D−1) bytes, the 3rd byte of every N-byte sequence by 2*(D−1) bytes and so forth. The example of FIG. 2B uses N=3 and D=2.
Encoder 12 passes the encoded data bytes 30 to interleaver 16. Interleaver 16 delays the first bytes (b0, b3, b6, b9) by 0 bytes, delays the 2nd bytes (b1,b4,b7,b10) by one (D−1) byte, and delays the 3rd bytes (b2, b5, b8, b11) by two (2*(D−1)) bytes. The interleaved data bytes 34 are transmitted over channel 20. Deinterleaver 24 finds the N (3) byte boundary and then delays the 1st bytes (b0, b3, b6, b9) by two bytes, i.e., (2*(D−1)) bytes, delays the 2nd bytes (b1, b4, b7) by one byte, i.e., (D−1) byte, and delays the 3rd bytes (b2, b5, b8, b11) by 0 bytes. The de-interleaved data 38 is then presented to decoder 26 for further processing.
Unlike BI, GCI repeats every N byte period, not every (N*D) byte period. Also, GCI requires that N and D are relatively prime.